{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Prime Number of Set Bits in Binary Representation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countPrimeSetBits"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #二进制表示中质数个计算置位"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个整数&nbsp;<code>left</code>&nbsp;和&nbsp;<code>right</code> ，在闭区间 <code>[left, right]</code>&nbsp;范围内，统计并返回 <strong>计算置位位数为质数</strong> 的整数个数。</p>\n",
    "\n",
    "<p><strong>计算置位位数</strong> 就是二进制表示中 <code>1</code> 的个数。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如， <code>21</code>&nbsp;的二进制表示&nbsp;<code>10101</code>&nbsp;有 <code>3</code> 个计算置位。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>left = 6, right = 10\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>\n",
    "6 -&gt; 110 (2 个计算置位，2 是质数)\n",
    "7 -&gt; 111 (3 个计算置位，3 是质数)\n",
    "9 -&gt; 1001 (2 个计算置位，2 是质数)\n",
    "10-&gt; 1010 (2 个计算置位，2 是质数)\n",
    "共计 4 个计算置位为质数的数字。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>left = 10, right = 15\n",
    "<strong>输出：</strong>5\n",
    "<strong>解释：</strong>\n",
    "10 -&gt; 1010 (2 个计算置位, 2 是质数)\n",
    "11 -&gt; 1011 (3 个计算置位, 3 是质数)\n",
    "12 -&gt; 1100 (2 个计算置位, 2 是质数)\n",
    "13 -&gt; 1101 (3 个计算置位, 3 是质数)\n",
    "14 -&gt; 1110 (3 个计算置位, 3 是质数)\n",
    "15 -&gt; 1111 (4 个计算置位, 4 不是质数)\n",
    "共计 5 个计算置位为质数的数字。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= left &lt;= right &lt;= 10<sup>6</sup></code></li>\n",
    "\t<li><code>0 &lt;= right - left &lt;= 10<sup>4</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [prime-number-of-set-bits-in-binary-representation](https://leetcode.cn/problems/prime-number-of-set-bits-in-binary-representation/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [prime-number-of-set-bits-in-binary-representation](https://leetcode.cn/problems/prime-number-of-set-bits-in-binary-representation/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['6\\n10', '10\\n15']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimeSetBits(self, left: int, right: int) -> int:\n",
    "        primes = {2, 3, 5, 7, 11, 13, 17, 19}\n",
    "        return sum(i.bit_count() in primes for i in range(left, right + 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def countPrimeSetBits(self, left: int, right: int) -> int:\n",
    "        ls=[]\n",
    "\n",
    "        ts=0\n",
    "        for i in range(left,right+1):\n",
    "            ls.append(i)\n",
    "        for i in range(len(ls)):\n",
    "            ls[i]=bin(ls[i])\n",
    "        for i in range(len(ls)):\n",
    "            b=str(ls[i])\n",
    "            sum = 0\n",
    "            for i in range(len(b)-2):\n",
    "                if b[i+2]=='1':\n",
    "                    sum+=1\n",
    "            if sum<=1 :\n",
    "                b=0\n",
    "            for i in range(2,int(math.sqrt(sum))+1):\n",
    "                if sum%i==0:\n",
    "                    b=0\n",
    "            if b !=0:\n",
    "                ts+=1\n",
    "        return  ts"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimeSetBits(self, left: int, right: int) -> int:\n",
    "        lst = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]\n",
    "        ans = 0\n",
    "        for num in range(left, right + 1):\n",
    "            a = bin(num).count(\"1\")\n",
    "            if a in lst:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimeSetBits(self, left: int, right: int) -> int:\n",
    "        def isPrime(num):\n",
    "            # 定义最小质因数为2\n",
    "            if num<2:\n",
    "                return False\n",
    "            flag = 2\n",
    "            while num > flag:\n",
    "                a = num % flag\n",
    "                if a == 0:\n",
    "                    return False\n",
    "                else:\n",
    "                    flag+=1\n",
    "            return True\n",
    "        aa = 0\n",
    "        for i in range(left,right+1):\n",
    "            a = bin(i)[2:].count(\"1\")\n",
    "            if isPrime(a):\n",
    "                aa+=1\n",
    "        return aa"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimeSetBits(self, left: int, right: int) -> int:\n",
    "        return sum((1 << x.bit_count()) & 665772 != 0 for x in range(left, right + 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimeSetBits(self, left: int, right: int) -> int:\n",
    "        def isPrime(num):\n",
    "            # 定义最小质因数为2\n",
    "            if num<2:\n",
    "                return False\n",
    "            flag = 2\n",
    "            while num > flag:\n",
    "                a = num % flag\n",
    "                if a == 0:\n",
    "                    return False\n",
    "                else:\n",
    "                    flag+=1\n",
    "            return True\n",
    "        aa = 0\n",
    "        for i in range(left,right+1):\n",
    "            a = bin(i)[2:].count(\"1\")\n",
    "            if isPrime(a):\n",
    "                aa+=1\n",
    "        return aa"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimeSetBits(self, left: int, right: int) -> int:\n",
    "        #边界条件  8.bit_count() wrong  (8).bit_count() decimal\n",
    "        def isprime(n):\n",
    "            if n ==1:\n",
    "                return False\n",
    "            if n ==2:\n",
    "                return True\n",
    "            for i in range(2,n):\n",
    "                if n  %i ==0:\n",
    "                    return False\n",
    "            return True\n",
    "        ans =0\n",
    "        for i in range(left,right+1):\n",
    "            cnt = i.bit_count()\n",
    "            if isprime(cnt):\n",
    "                ans +=1\n",
    "        return ans\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimeSetBits(self, left: int, right: int) -> int:\n",
    "        res = 0\n",
    "        h = [2,3,5,7,11,13,17,19]\n",
    "        for value in range(left,right + 1):\n",
    "            n = 0\n",
    "            while value > 0:\n",
    "                value &= (value - 1)\n",
    "                n += 1\n",
    "            if n in h:\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimeSetBits(self, left: int, right: int) -> int:\n",
    "        def isPrime(n):\n",
    "            if n == 1:\n",
    "                return False\n",
    "            for i in range(2, n//2+1):\n",
    "                if n % i == 0:\n",
    "                    return False\n",
    "            return True\n",
    "        ans = 0\n",
    "        for num in range(left, right + 1):\n",
    "            s = sum([int(i) for i in bin(num)[2:]])\n",
    "            ans += 1 if isPrime(s) else 0\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimeSetBits(self, left: int, right: int) -> int:\n",
    "        return sum(((1 << x.bit_count()) & 665772) != 0 for x in range(left, right + 1))\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimeSetBits(self, left: int, right: int) -> int:\n",
    "        ans = 0\n",
    "        for i in range(left,right+1):\n",
    "            i = bin(i)\n",
    "            count1 = i.count('1')\n",
    "            if count1 in [2,3,5,7,11,13,17,19]:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "PRIMES = {2, 3, 5, 7, 11, 13, 17, 19}\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countPrimeSetBits(self, left: int, right: int) -> int:\n",
    "        return sum(i.bit_count() in PRIMES for i in range(left, right + 1))\n",
    "\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    left, right = 6, 10\n",
    "    res = Solution().countPrimeSetBits(left, right)\n",
    "    print(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "G = {2,3,5,7,11,13,17,19}\n",
    "class Solution:\n",
    "    def countPrimeSetBits(self, left: int, right: int) -> int:\n",
    "        return sum(bin(i).count('1') in G for i in range(left, right+1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimeSetBits(self, left: int, right: int) -> int:\n",
    "        primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 27, 29, 31]\n",
    "        res = 0\n",
    "        for x in range(left, right + 1):\n",
    "            cnt = sum([1 for i in str(bin(x))[2:] if i == '1'])\n",
    "            if cnt in primes:\n",
    "                res += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimeSetBits(self, left: int, right: int) -> int:\n",
    "        def Prime(s):\n",
    "            \n",
    "            k = sum([int(i) for i in s])\n",
    "            if k == 1:\n",
    "                return 0\n",
    "            else:\n",
    "                a = 0\n",
    "                for i in range(1,k+1):\n",
    "                    if k%i==0:\n",
    "                        a+=1\n",
    "                if a == 2:\n",
    "                    return 1\n",
    "                return 0\n",
    "\n",
    "\n",
    "        lis = [bin(i)[2:] for i in range(left,right+1)]\n",
    "        m = 0\n",
    "        for i in lis:\n",
    "            m+=Prime(i)\n",
    "        return m\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimeSetBits(self, left: int, right: int) -> int:\n",
    "        def isPrime(num):\n",
    "            if num<2:\n",
    "                return False\n",
    "            flag = 2\n",
    "            while num > flag:\n",
    "                a = num % flag\n",
    "                if a == 0:\n",
    "                    return False\n",
    "                else:\n",
    "                    flag+=1\n",
    "            return True\n",
    "        aa = 0\n",
    "        for i in range(left,right+1):\n",
    "            a = bin(i)[2:].count(\"1\")\n",
    "            if isPrime(a):\n",
    "                aa+=1\n",
    "        return aa"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimeSetBits(self, left: int, right: int) -> int:\n",
    "        def count_one(num):\n",
    "            res = 0\n",
    "            while num:\n",
    "                res += num & 1\n",
    "                num >>= 1\n",
    "            if res <= 1:\n",
    "                return False\n",
    "            elif res == 2:\n",
    "                return True\n",
    "            else:\n",
    "                for x in range(2, int(res ** 0.5)+1):\n",
    "                    if res % x == 0:\n",
    "                        return False\n",
    "                return True\n",
    "        res = 0\n",
    "        for x in range(left, right+1):\n",
    "            if count_one(x):\n",
    "                res += 1\n",
    "        return res\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimeSetBits(self, left: int, right: int) -> int:\n",
    "        res = 0\n",
    "        for i in range(left,right+1):\n",
    "            c = str(bin(i)).count(\"1\")\n",
    "            if c in [2,3,5,7,11,13,17,19]:\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimeSetBits(self, left: int, right: int) -> int:\n",
    "        \"\"\"\n",
    "        功能描述：给两个整数left和right，在闭区间[left, right]范围内，统计并返回计算置位位数为质数的\n",
    "                 整数个数。\n",
    "        参数：left -- int\n",
    "              right -- int\n",
    "        返回值：res -- int\n",
    "        \"\"\"\n",
    "        def isPrime(x:int) -> int:\n",
    "            prime = []\n",
    "            for i in range(1, x+1):\n",
    "                if x % i == 0:\n",
    "                    prime.append(i)\n",
    "            if len(prime) == 2:\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "\n",
    "\n",
    "        res = 0\n",
    "        binary = [bin(i)[2:] for i in range(left, right+1)]\n",
    "        binary_count = [binary[i].count('1') for i in range(len(binary))]\n",
    "        \n",
    "        for num in binary_count:\n",
    "            if isPrime(num):\n",
    "                res += 1\n",
    "\n",
    "            #prime = []\n",
    "            #if num == 1:\n",
    "            #    continue\n",
    "            #else:\n",
    "            #    for j in range(2,num+1):\n",
    "            #        if num % j == 0:\n",
    "            #            prime.append(num)\n",
    "            #if len(prime) < 2:\n",
    "            #    res += 1\n",
    "        \n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimeSetBits(self, left: int, right: int) -> int:\n",
    "        def isPrime(num: int) -> int:\n",
    "            if num <= 1:\n",
    "                return 0\n",
    "            for j in range(2, floor(num ** 0.5) + 1):\n",
    "                if num % j == 0:\n",
    "                    return 0\n",
    "            return 1\n",
    "\n",
    "        count = 0\n",
    "        for i in range(left, right + 1):\n",
    "            count += isPrime(bin(i).count('1'))\n",
    "        return count\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimeSetBits(self, left: int, right: int) -> int:\n",
    "        def judge(n):\n",
    "            if n < 2:\n",
    "                return False\n",
    "            start = 2\n",
    "            while start * start <= n:\n",
    "                if not n % start:\n",
    "                    return False\n",
    "                start += 1\n",
    "            return True\n",
    "        \n",
    "        def counts(n):\n",
    "            ans = 0\n",
    "            while n:\n",
    "                if n & 1 == 1:\n",
    "                    ans += 1\n",
    "                n >>= 1\n",
    "            return ans\n",
    "        \n",
    "        return sum(1 for num in range(left,right+1) if judge(counts(num)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimeSetBits(self, left: int, right: int) -> int:\n",
    "        ans = 0\n",
    "        for i in range(left,right+1):\n",
    "            i = bin(i)\n",
    "            count1 = i.count('1')\n",
    "            if count1 in [2,3,5,7,11,13,17,19]:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimeSetBits(self, left: int, right: int) -> int:\n",
    "        arr = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]\n",
    "        return sum(num.bit_count() in arr for num in range(left, right + 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPrime(self, x: int) -> bool:\n",
    "        if x < 2:\n",
    "            return False\n",
    "        i = 2\n",
    "        while i * i <= x:\n",
    "            if x % i == 0:\n",
    "                return False\n",
    "            i += 1\n",
    "        return True\n",
    "\n",
    "    def countPrimeSetBits(self, left: int, right: int) -> int:\n",
    "        return sum(self.isPrime(x.bit_count()) for x in range(left, right + 1))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimeSetBits(self, left: int, right: int) -> int:\n",
    "        ans = 0\n",
    "        for i in range(left,right+1):\n",
    "            i = bin(i)\n",
    "            i = i[2:]\n",
    "            count1 = i.count('1')\n",
    "            if count1 in [2,3,5,7,11,13,17,19,23,29,31]:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimeSetBits(self, left: int, right: int) -> int:\n",
    "        a=[]\n",
    "        b=[2,3,5,7,11,13,17,19]\n",
    "        for i in range(left,right+1):\n",
    "            a.append(bin(i)[2:].count('1'))\n",
    "        c=len(a)\n",
    "        for i in a:\n",
    "            if i not in b:\n",
    "                c-=1\n",
    "        return c\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countPrimeSetBits(self, left: int, right: int) -> int:\n",
    "         ans=0\n",
    "         for i in range(left,right+1):\n",
    "             a=bin(i).count(\"1\")\n",
    "             if is_true(a):\n",
    "                ans+=1\n",
    "         return ans\n",
    "def is_true(x):\n",
    "        for j in range(2,x):\n",
    "            if x%j==0:\n",
    "                return False\n",
    "        return x>1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "PRIMES={2,3,5,7,11,13,17,19}\n",
    "class Solution:\n",
    "    def countPrimeSetBits(self, left: int, right: int) -> int:\n",
    "        return sum(i.bit_count() in PRIMES for i in range(left,right+1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimeSetBits(self, left: int, right: int) -> int:\n",
    "        res = 0\n",
    "        self.dp = {}\n",
    "        for num in range(left, right+1):\n",
    "            x = self.count_one(num, self.dp)\n",
    "            if self.is_prime(x):\n",
    "                res += 1\n",
    "        return res\n",
    "\n",
    "    def count_one(self, num, dp):\n",
    "        if num in dp:\n",
    "            return dp[num]\n",
    "        if num == 0:\n",
    "            return 0\n",
    "        \n",
    "        dp[num] = self.count_one(num-(num&(-num)), dp) + 1\n",
    "        return dp[num]\n",
    "        \n",
    "    def is_prime(self, x):\n",
    "        # 小于 2 的一定不是质数\n",
    "        if x < 2:\n",
    "            return False\n",
    "        # 合数的最大因子因子只能有一个大与sqt(x)\n",
    "        i = 2\n",
    "        while i * i <= x:\n",
    "            if x % i == 0:\n",
    "                return False\n",
    "            i += 1\n",
    "        \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimeSetBits(self, left: int, right: int) -> int:     \n",
    "        primes={2,3,5,7,11,13,17,19}\n",
    "\n",
    "        result=0\n",
    "        last=left.bit_count()\n",
    "        if last in primes:\n",
    "            result+=1\n",
    "        for i in range(left+1,right+1):\n",
    "            if i%2==1:\n",
    "                last+=1\n",
    "                if last in primes:\n",
    "                    result+=1\n",
    "            else:\n",
    "                last=i.bit_count()\n",
    "                if last in primes:\n",
    "                    result+=1\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimeSetBits(self, left: int, right: int) -> int:\n",
    "        def pn (n:int) -> bool:\n",
    "            flag=True\n",
    "            for i in range(2,n):\n",
    "                if n%i == 0:\n",
    "                    flag=False\n",
    "            return flag\n",
    "        count=0\n",
    "        for i in range(left,right+1):\n",
    "            s=str(bin(i)).count('1')\n",
    "            #print(i,bin(i))\n",
    "            if pn(s) and s>1:\n",
    "                count+=1\n",
    "        return count\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimeSetBits(self, left: int, right: int) -> int:     \n",
    "        primes={2,3,5,7,11,13,17,19}\n",
    "\n",
    "        result=0\n",
    "        last=left.bit_count()\n",
    "        last_is_even=left%2==0\n",
    "        if last in primes:\n",
    "            result+=1\n",
    "        for i in range(left+1,right+1):\n",
    "            if last_is_even:\n",
    "                last+=1\n",
    "                if last in primes:\n",
    "                    result+=1\n",
    "            else:\n",
    "                last=i.bit_count()\n",
    "                if last in primes:\n",
    "                    result+=1\n",
    "            last_is_even=not last_is_even\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import sqrt\n",
    "class Solution:\n",
    "    def countPrimeSetBits(self, left: int, right: int) -> int:\n",
    "        count = 0\n",
    "        for i in range(left, right+1):\n",
    "            Sbin = bin(i)[2:]\n",
    "            num = Sbin.count(\"1\")\n",
    "            if self.is_prime(num):\n",
    "                count += 1\n",
    "        return count\n",
    "\n",
    "    def is_prime(self, num: int) -> bool:\n",
    "        if num <= 1:\n",
    "            return False\n",
    "        if num > 1 and num <= 3:\n",
    "            return True\n",
    "        i = 2\n",
    "        while i <= sqrt(num):\n",
    "            if num % i == 0:\n",
    "                return False\n",
    "            i += 1\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimeSetBits(self, left: int, right: int) -> int:\n",
    "        mp = {2, 3, 5, 7, 11, 13, 17, 19}\n",
    "        ans = 0\n",
    "        for i in range(left, right + 1):\n",
    "            cnt = 0\n",
    "            for k in range(20):\n",
    "                cnt += i & 1\n",
    "                i >>= 1\n",
    "            if cnt in mp:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def countPrimeSetBits(self, left: int, right: int) -> int:\r\n",
    "        primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]\r\n",
    "        primes = {i: 1 for i in primes}\r\n",
    "        ans = 0\r\n",
    "        for x in range(left, right + 1):\r\n",
    "            cnt = 0\r\n",
    "            while x:\r\n",
    "                cnt += x&1\r\n",
    "                x >>= 1\r\n",
    "            if primes.get(cnt):\r\n",
    "                ans += 1\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimeSetBits(self, left: int, right: int) -> int:\n",
    "        count = 0\n",
    "        prime = [2,3,5,7,11,13,17,19]\n",
    "        for i in range(left, right+1):\n",
    "            if i.bit_count() in prime:\n",
    "                count += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimeSetBits(self, left: int, right: int) -> int:\n",
    "        def is_prime(x):\n",
    "            if x < 2:\n",
    "                return False \n",
    "            i = 2 \n",
    "            while i * i <= x:\n",
    "                if x % i == 0:\n",
    "                    return False \n",
    "                i += 1\n",
    "            return True\n",
    "        ans = 0\n",
    "        for i in range(left, right+1):\n",
    "            b = i.bit_count()\n",
    "            if is_prime(b):\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimeSetBits(self, left: int, right: int) -> int:\n",
    "        集合 = set((2,3,5,7,11,13,17,19,21,23))\n",
    "        质数个数 = 0\n",
    "        for i in range(left, right+1):\n",
    "            x = i.bit_count()\n",
    "            if x == 1:\n",
    "                continue\n",
    "            if x in 集合:\n",
    "                质数个数 += 1\n",
    "            else:\n",
    "                for j in range(2, x):\n",
    "                    if not x%j:\n",
    "                        break\n",
    "                else:\n",
    "                    质数个数 += 1\n",
    "                    集合.add(x)\n",
    "        return 质数个数"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimeSetBits(self, left: int, right: int) -> int:\n",
    "        s=0\n",
    "        a=[]\n",
    "        for i in range(left,right+1):\n",
    "            b=0\n",
    "            for j in str(bin(i)):\n",
    "                if j==\"1\":\n",
    "                    b+=1\n",
    "            a.append(b)\n",
    "        for i in a:\n",
    "            if i==1:\n",
    "                continue\n",
    "            for j in range(2,i):\n",
    "                if i%j==0:\n",
    "                    break\n",
    "            else:\n",
    "                s+=1\n",
    "        return s\n",
    "            \n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimeSetBits(self, left: int, right: int) -> int:\n",
    "        def is_prime(n) -> bool:\n",
    "            if n < 2:\n",
    "                return False\n",
    "            i = 2\n",
    "            while i * i <= n:\n",
    "                if n % i == 0:\n",
    "                    return False\n",
    "                i += 1\n",
    "            return True\n",
    "        return sum(is_prime(i.bit_count()) for i in range(left, right + 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimeSetBits(self, left: int, right: int) -> int:\n",
    "\n",
    "        def isPrime(x):\n",
    "            x = x.bit_count()\n",
    "            if x < 2:\n",
    "                return False\n",
    "            i = 2\n",
    "\n",
    "            while i * i <= x:\n",
    "                if x % i == 0:\n",
    "                    return False \n",
    "                i += 1\n",
    "            \n",
    "            return True\n",
    "        \n",
    "        return sum(isPrime(x) for x in range(left, right + 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimeSetBits(self, left: int, right: int) -> int:\n",
    "        return sum(((1 << x.bit_count()) & 665772) != 0 for x in range(left, right + 1))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def countPrimeSetBits(self, left: int, right: int) -> int:\r\n",
    "        prime = set([2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31])\r\n",
    "        res = 0\r\n",
    "        for num in range(left, right + 1):\r\n",
    "            if bin(num).count('1') in prime:\r\n",
    "                res += 1\r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimeSetBits(self, left: int, right: int) -> int:\n",
    "        集合 = set((2,3,5,7,11,13,17,19,21,23))\n",
    "        质数个数 = 0\n",
    "        for i in range(left, right+1):\n",
    "            x = i.bit_count()\n",
    "            if x == 1:\n",
    "                continue\n",
    "            if x in 集合:\n",
    "                质数个数 += 1\n",
    "            else:\n",
    "                y = 1\n",
    "                while y*y <= x:\n",
    "                    if not x%y:\n",
    "                        break\n",
    "                else:\n",
    "                    质数个数 += 1\n",
    "                    集合.add(x)\n",
    "        return 质数个数"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimeSetBits(self, left: int, right: int) -> int:     \n",
    "        primes={2,3,5,7,11,13,17,19}\n",
    "\n",
    "        result=0\n",
    "        last=left.bit_count()\n",
    "        if last in primes:\n",
    "            result+=1\n",
    "        for i in range(left+1,right+1):\n",
    "            if i%2==1:\n",
    "                last+=1\n",
    "                if last in primes:\n",
    "                    result+=1\n",
    "            else:\n",
    "                n=0\n",
    "                while i%2==0:\n",
    "                    i/=2\n",
    "                    n+=1\n",
    "                last+=1-n\n",
    "                if last in primes:\n",
    "                    result+=1\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimeSetBits(self, left: int, right: int) -> int:\n",
    "        count = 0\n",
    "        hax = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31}\n",
    "        for x in range(left, right+1):\n",
    "            if x.bit_count() in hax:\n",
    "                count += 1\n",
    "        return count\n",
    "\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimeSetBits(self, left: int, right: int) -> int:\n",
    "\n",
    "        def judge(n:int):\n",
    "            if n ==1:return False\n",
    "            for i in range(2, n):\n",
    "                if n%i==0:return False\n",
    "            return True\n",
    "\n",
    "        sum=0\n",
    "        for i in range(left,right+1):\n",
    "            binnum = bin(i).count('1')\n",
    "            if(judge(binnum)):\n",
    "                sum=sum+1\n",
    "        return sum\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimeSetBits(self, left: int, right: int) -> int:\n",
    "        def ePrime(n): # include n\n",
    "            primes = [False] * 2 + [True] * (n - 1)\n",
    "            for i in range(2, n + 1):\n",
    "                if primes[i]:\n",
    "                    for j in range(i * i, n + 1, i):\n",
    "                        primes[j] = False\n",
    "            return primes\n",
    "        \n",
    "        primes, res = ePrime(32), 0\n",
    "        for n in range(left, right + 1):\n",
    "            c = n.bit_count()\n",
    "            if primes[c]:\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimeSetBits(self, left: int, right: int) -> int:\n",
    "        def isPrimeNum(a):\n",
    "            if a==1:\n",
    "                return False\n",
    "            for i in range(2,a//2+1):\n",
    "                if a%i==0:\n",
    "                    return False\n",
    "            return True\n",
    "        temp=0\n",
    "        for i in range(left,right+1):\n",
    "            s=bin(i).lstrip('0b')\n",
    "            b=s.count('1')\n",
    "            if isPrimeNum(b):\n",
    "                temp+=1\n",
    "        return temp\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution():\n",
    "\n",
    "    def countPrimeSetBits(self, num1, num2):\n",
    "        '''\n",
    "        给定一个闭区间[num1,num2],计算统计并返回计算置位为质数的整数个数\n",
    "        :param num1: 闭区间的启始数\n",
    "        :param num2: 闭区间的结束数\n",
    "        :return: 质数位数为质数的整数个数(int)\n",
    "        '''\n",
    "        result=0    #存储统计结果数量\n",
    "        for now_num in range(num1,num2+1):      #遍历闭区间的每一个数\n",
    "            now_num_byte=bin(now_num).replace('0b','')  #将当前遍历到的数转换为二进制数,并将0b开头的标志符去除,获取到str类型的二进制数\n",
    "            now_num_1_num=now_num_byte.count('1')       #统计二进制数中1的数量\n",
    "            if self.is_zhishu(now_num_1_num) == True:   #调用函数is_zhishu判定1的数量是否为质数\n",
    "                result+=1   #如果是质数则结果+1\n",
    "        return result   #遍历完成返回最终结果\n",
    "\n",
    "\n",
    "    def is_zhishu(self,num):\n",
    "        '''\n",
    "\n",
    "        判定一个数字是否为质数\n",
    "        :param num: 一个数字\n",
    "        :return: True表示为质数,False表示不是质数\n",
    "        '''\n",
    "\n",
    "        if num <= 1:\n",
    "            return False\n",
    "\n",
    "        for i in range(2,num // 2+1):\n",
    "            if num % i == 0:\n",
    "                return False\n",
    "\n",
    "        return True\n",
    "\n",
    "\n",
    "# if __name__ == \"__main__\":\n",
    "#     the_Solution = Solution()\n",
    "#     left_num = input(\"left=\")\n",
    "#     right_num = input\n",
    "#     the_result = the_Solution.count(10,15)\n",
    "#     print(the_result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimeSetBits(self, left: int, right: int) -> int:\n",
    "        s=0\n",
    "        a=[]\n",
    "        for i in range(left,right+1):\n",
    "            b=0\n",
    "            for j in str(bin(i)):\n",
    "                if j==\"1\":\n",
    "                    b+=1\n",
    "            a.append(b)\n",
    "        for i in a:\n",
    "            if i==1:\n",
    "                continue\n",
    "            for j in range(2,i):\n",
    "                if i%j==0:\n",
    "                    break\n",
    "            else:\n",
    "                s+=1\n",
    "        return s\n",
    "            \n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimeSetBits(self, left: int, right: int) -> int:\n",
    "        def getBit(num:int)->int:\n",
    "            count=0\n",
    "            while num:\n",
    "                num&=(num-1)\n",
    "                count+=1\n",
    "            return count\n",
    "        def isPrime(num:int)->bool:\n",
    "            if num<2:\n",
    "                return False\n",
    "            fact=2\n",
    "            while fact*fact<=num:\n",
    "                if num%fact==0:\n",
    "                    return False\n",
    "                fact+=1\n",
    "            return True\n",
    "        return sum(isPrime(getBit(x))for x in range(left,right+1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def countPrimeSetBits(self, left: int, right: int) -> int:\r\n",
    "        primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]\r\n",
    "        ans = 0\r\n",
    "        for x in range(left, right + 1):\r\n",
    "            cnt = 0\r\n",
    "            while x:\r\n",
    "                cnt += x&1\r\n",
    "                x >>= 1\r\n",
    "            if cnt in primes:\r\n",
    "                ans += 1\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPrime(self, x: int) -> bool:\n",
    "        if x < 2:\n",
    "            return False\n",
    "        i = 2\n",
    "        while i * i <= x:\n",
    "            if x % i == 0:\n",
    "                return False\n",
    "            i += 1\n",
    "        return True\n",
    "\n",
    "    def countPrimeSetBits(self, left: int, right: int) -> int:\n",
    "        return sum(self.isPrime(x.bit_count()) for x in range(left, right + 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimeSetBits(self, left: int, right: int) -> int:\n",
    "        ans = 0\n",
    "        for i in range(left,right+1):\n",
    "            i = bin(i)\n",
    "            i = i[2:]\n",
    "            count1 = i.count('1')\n",
    "            if count1 in [2,3,5,7,11,13,17,19]:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimeSetBits(self, left: int, right: int) -> int:\n",
    "        ans = 0\n",
    "        for i in range(left,right+1):\n",
    "            i = bin(i)\n",
    "            i = i[2:]\n",
    "            count1 = i.count('1')\n",
    "            if count1 in [2,3,5,7,11,13,17,19,23,29,31]:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judge(self, num: int) -> bool:\n",
    "        x = 0\n",
    "        while num:\n",
    "            if num & 1 == 1:\n",
    "                x += 1\n",
    "            num = num >> 1\n",
    "        if x==1: return False\n",
    "        for i in range(2, int(x**0.5) + 1):\n",
    "            if x % i == 0:\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "    def countPrimeSetBits(self, left: int, right: int) -> int:\n",
    "        ans = 0\n",
    "        for i in range(left, right + 1):\n",
    "            if self.judge(i):\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimeSetBits(self, left: int, right: int) -> int:\n",
    "        ans = 0\n",
    "        for i in range(left,right+1):\n",
    "            i = bin(i)\n",
    "            i = i[2:]\n",
    "            count1 = i.count('1')\n",
    "            if count1 in [2,3,5,7,11,13,17,19,23,29,31]:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimeSetBits(self, left: int, right: int) -> int:\n",
    "        return sum(((1 << x.bit_count()) & 665772) != 0 for x in range(left, right + 1))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimeSetBits(self, left: int, right: int) -> int:\n",
    "        return sum((1<<i.bit_count())&665772!=0 for i in range(left,right+1) )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 一般解法，时间复杂度为O(logN * N**0.5)\n",
    "    def isPrime(self, x: int) -> bool:\n",
    "        if x < 2:\n",
    "            return False\n",
    "        i = 2\n",
    "        while i * i <= x:\n",
    "            if x % i == 0:\n",
    "                return False\n",
    "            i += 1\n",
    "        return True\n",
    "\n",
    "    def countPrimeSetBits(self, left: int, right: int) -> int:\n",
    "        return sum(self.isPrime(x.bit_count()) for x in range(left, right + 1))\n",
    "\n",
    "    # 优化版本，因为right≤106<220，因此二进制中 1 的个数不会超过 19，而不超过 19 的质数只有\n",
    "#          2,3,5,7,11,13,17,19\n",
    "# 我们可以用一个二进制数 mask=665772=10100010100010101100​ 来存储这些质数，其中 mask 二进制的从低到高的第 i 位为 1 表示 i 是质数，为 0 表示 i 不是质数。\n",
    "# 设整数 xxx 的二进制中 1 的个数为 c，若 mask 按位与  不为 0，则说明 c 是一个质数。\n",
    "    def countPrimeSetBits(self, left: int, right: int) -> int:\n",
    "        # x.bit_count()返回二进制中1的个数，若是质数，则在自己对应的位置上肯定是1\n",
    "        return sum(((1 << x.bit_count()) & 665772) != 0 for x in range(left, right + 1))\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimeSetBits(self, left: int, right: int) -> int:       \n",
    "            res = 0\n",
    "       \n",
    "            for i in range(left, right + 1):\n",
    "                c = bin(i).count('1')\n",
    "                \n",
    "                if c > 1:\n",
    "                    f = 1\n",
    "                    for j in range(2, c):\n",
    "                        if c % j == 0:\n",
    "                            f = 0\n",
    "                            break\n",
    "                    if f:      \n",
    "                        res += 1\n",
    "                    \n",
    "            return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimeSetBits(self, left: int, right: int) -> int:\n",
    "        def judge(num) -> bool:\n",
    "            if num == 1 or num == 0:\n",
    "                return False\n",
    "            for i in range(2, int(num ** 0.5) + 1):\n",
    "                if num % i == 0:\n",
    "                    return False\n",
    "            return True\n",
    "        count = 0\n",
    "        for num in range(left, right + 1):\n",
    "            if judge(bin(num).count('1')):\n",
    "                count += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimeSetBits(self, left: int, right: int) -> int:\n",
    "        def judge(n:int):\n",
    "            if n == 1 :\n",
    "                return False\n",
    "            else:\n",
    "                l = 2\n",
    "                while l<n:\n",
    "                    if n % l == 0:\n",
    "                        return False\n",
    "                    l += 1\n",
    "                return True\n",
    "        count = 0\n",
    "        while left <= right:\n",
    "            bin_num = bin(left)\n",
    "            count1 = bin_num.count('1')\n",
    "            if judge(count1):\n",
    "                count += 1\n",
    "            left += 1\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimeSetBits(self, left: int, right: int) -> int:\n",
    "        count = 0\n",
    "        for i in range(left, right+1):\n",
    "            temp = bin(i)\n",
    "            if self.isZhiShu(temp.count('1')):\n",
    "                count += 1\n",
    "        return count\n",
    "    def isZhiShu(self, x: int) -> bool:\n",
    "        if x == 1:\n",
    "            return False\n",
    "        for i in range(2,int(x**0.5)+1):\n",
    "            if x % i == 0:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "PRIMES = {2, 3, 5, 7, 11, 13, 17, 19}\n",
    "\n",
    "class Solution:\n",
    "    def countPrimeSetBits(self, left: int, right: int) -> int:\n",
    "        return sum(x.bit_count() in PRIMES for x in range(left, right + 1))"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
